The following abbreviations are herewith expanded, at least some of which are referred to within the following description of the state-of-the-art and the present invention.
DP Dual Port [memory]
DRAM Dynamic RAM
IEEE Institute of Electrical and Electronics Engineers
ITU International Telecommunication Union
RAM Random Access Memory
SRAM Static RAM
Digital systems typically require rapid movement of data for efficient computing and communications. Interconnection networks are needed to provide high-bandwidth, low-latency communication between nodes in a network. Interconnection networks can be found, for example, in network routers, input/output and storage switches, processor-memory and inter-processor communication networks, and systems-on-a-chip (SoC).
An interconnection network is considered to be non-blocking if it can handle all circuit requests that are a permutation of the inputs and the outputs. This implies that a dedicated path can be formed from each input to its selected output. Crossbar topologies achieve such non-blocking connectivity, but they do not scale very well. The massive growth of digital systems and communication networks puts ever more demanding requirements on its components and its interconnection networks. For instance, in optical transport networks, channels nowadays operate at 100 Gb/s and beyond per wavelength, and accordingly, core and edge routers have to process tremendous amounts of information. This disclosure submission primarily focuses on the design of an interconnection network for switches and routers, but the solutions are also directly applicable to general interconnection networks in digital systems.
A router is typically characterized by the number of input ports, the number of output ports, and the overall throughput. Routers read the header information of each packet and extract the destination address, in order to direct the packet to its destination. Routers typically consist of a large number of line cards and a smaller number of cards with switch fabric.
The switch fabric, which frequently resides in ASICs, is tasked to provide arbitrary connectivity, in parallel, between the input ports and output ports. Incoming traffic is controlled by buffer managers, which typically reside on the line cards, and queue managers, which control the switch fabric.
The switching fabric typically uses a butterfly topology to connect the input ports to the output ports. From the point of a single input port, the butterfly looks like a tree. Each level of the tree contains switching nodes, which pass packets along. Switching fabric is most commonly implemented as a three-stage network, in which each stage is composed of a number of crossbar switches.
Such a network is referred to as a Clos network. A symmetric Clos network is characterized by a 3-tuple (m,n,r), where m denotes the number of middle-stage switches, n denotes the number of input (output) ports on each input (output) switch, and r denotes the number of input and output switches. Every component switch has a parser. Clos networks with more than three stages exist. A Clos network that is composed of 2×2 switches is also referred to as a Benes network.
These networks are generally, but not strictly non-blocking, and they also suffer from excessive control and overhead to make them generally non-blocking. As such, these interconnection networks become ever more complex, do not scale very well, and there are no viable guaranteed non-blocking solutions.
Alternative non-blocking switching architectures, such as the crossbar switch, suffer from poor scalability as their number of connections and buffering resources grows with the square of the number of ports. For all conventional switching architectures, the amount of internal memory is very large and grows faster than linearly with the traffic volume and the number of ports, which makes it difficult to scale such networks.
The technical problem that is addressed in this disclosure then is a need for a non-blocking switch fabric that is scalable, hardware-efficient, and energy-efficient. Currently-used switch fabrics typically do not have a guaranteed non-blocking property, which leads to packet loss, jitter, and latency. Many switch fabric architectures also does not scale very well and require increasingly complicated routing control to have reasonable non-blocking performance One objective of the present solution is to design a new switch fabric architecture that meets stringent requirements on throughput, and strict constraints on latency and power consumption.
These and other problems are addressed by the apparatus and method of the proposed solution. Note that although is provided as background for the description, no admission is made or intended that the information herein is known to others besides the inventors. Note also that while there are certain stated or implied goals or objectives of the proposed solution, no level of performance is a requirement of the claimed invention unless recited explicitly in a particular embodiment.